/*
给定一个链表，返回链表开始入环的第一个节点;如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。
说明：不允许修改给定的链表。
1->2->3->4->5
       <-----
环从尾部(5)连接到了3，则pos=2
*/

node*chain::isRing(){
    node*fast=head;
    node*slow=head;
    node*result=0;
    //寻找环的过程
    //快指针每次移动2个节点，慢指针每次移动1个节点
    while(fast!=0&&fast->next!=0){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){
            node*ptr=head;
            node*ptrFast=fast;
            /*
            当快慢指针相遇后，定义一个从头节点开始移动的指针、一个从相遇点开始移动的指针。
            两个指针相遇的位置即为环入口。
            推导：设环起点之前有x个节点，环起点到相遇点有y个节点，相遇点到环起点有z个节点。
            满足条件：slowWay=x+y;fastWay=x+y+n*(y+z);fastWay=2*slowWay
            推导得到：x=(n-1)(y+z)+z。
            不用考虑其他可能的位置情况，考虑最简单的情况即可。
            */
            while(ptr!=ptrFast){
                ptr=ptr->next;
                ptrFast=ptrFast->next;
            }
            result=ptr;
            break;
        }
    }
    return result;
}